week6 HW 戴偉璿
第一題
假設一開始的陣列都只有一格
a.
時間複雜度的部份,我們先假設n=2a+b;a,b∈N;b<2a+1,很顯然所需的複製次數為k=0∑a2k=2a+1−1,插入元素的複雜度為b,其時間雜度為O(2a+1+b)=O(2n)=O(n)
空間複雜度的部份,最終所需的空間為O(2a+1)=O(2n)=O(n)
b.
在插入新元素時,會先新增一個比原大小多一的陣列,並且將舊有的所有資料複製過去,由於每次都只會開「剛剛好」,因此空間複雜度為O(n)
但是每次都會將舊有的所有資料複製過去,在插入第二個元素時有一個元素需要複製,拆入第二個元素時需要複製兩個元素…插入第n個元素時需要複製n−1個元素。所需時間複雜度為每次操作時所需複製元素數目的總和,i=1∑n−1=2(n−1)n,big−O=O(n2)
第二題
事先聲明:kn=n除以k之後無條件捨去取至整數(跟C++一樣)
a.
預處理:O(NK)
總詢問:O(Q×KN)
b.
根據2.(a)的答案,預處理複雜度為O(NK),總詢問複雜度為O(Q×KN)。又O(N)=O(Q)
因此NK=Q×KN⇒K=N
c.
jump[i][j−1][1]+jump[jump[i][j−1]][1]][K][0]
e.
題目怪怪的?條件為j=1或j>0欸
ifj=1
jump[i][j][l]=jump[i][K][0]
ifj>1
jump[i][j][l]=jump[i][j−1][l]+jump[jump[i][j−1]][l]][K][l−1]